/*
 * @lc app=leetcode.cn id=450 lang=cpp
 *
 * [450] 删除二叉搜索树中的节点
 *
 * https://leetcode-cn.com/problems/delete-node-in-a-bst/description/
 *
 * algorithms
 * Medium (50.54%)
 * Likes:    729
 * Dislikes: 0
 * Total Accepted:    105.4K
 * Total Submissions: 208.6K
 * Testcase Example:  '[5,3,6,2,4,null,7]\n3'
 *
 * 给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key
 * 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
 * 
 * 一般来说，删除节点可分为两个步骤：
 * 
 * 
 * 首先找到需要删除的节点；
 * 如果找到了，删除它。
 * 
 * 
 * 
 * 
 * 示例 1:
 * 
 * 
 * 
 * 
 * 输入：root = [5,3,6,2,4,null,7], key = 3
 * 输出：[5,4,6,2,null,null,7]
 * 解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
 * 一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
 * 另一个正确答案是 [5,2,6,null,4,null,7]。
 * 
 * 
 * 
 * 
 * 示例 2:
 * 
 * 
 * 输入: root = [5,3,6,2,4,null,7], key = 0
 * 输出: [5,3,6,2,4,null,7]
 * 解释: 二叉树不包含值为 0 的节点
 * 
 * 
 * 示例 3:
 * 
 * 
 * 输入: root = [], key = 0
 * 输出: []
 * 
 * 
 * 
 * 提示:
 * 
 * 
 * 节点数的范围 [0, 10^4].
 * -10^5 <= Node.val <= 10^5
 * 节点值唯一
 * root 是合法的二叉搜索树
 * -10^5 <= key <= 10^5
 * 
 * 
 * 
 * 
 * 进阶： 要求算法时间复杂度为 O(h)，h 为树的高度。
 * 
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {

// //迭代遍历
// public:
//     TreeNode* deleteNode(TreeNode* root, int val) {
//         if(root == NULL) return NULL;

//         TreeNode* cur = root;
//         TreeNode* parent = NULL;

//         while(cur != NULL && cur->val != val) {
//             parent = cur;
//             if(cur->val > val) cur = cur->left;
//             else cur = cur->right;
//         }

//         //  while (cur) {
//         //     if (cur->val == val) break;
//         //     parent = cur;
//         //     if (cur->val > val) cur = cur->left;
//         //     else cur = cur->right;
//         // }

//         if(!parent) {
//             // // 以下这句话运行不通
//             // root =  deleteNode(root);

//             //直接返回就行？？？？？？？？？？
//             return deleteNode(root);
//         }
//         if(parent->left && parent->left->val == val) {
//             parent->left = deleteNode(cur);
//         } 
//         if(parent->right && parent->right->val == val) {
//             parent->right = deleteNode(cur);
//         }

//         return root;
//     }
// private:
//     TreeNode* deleteNode(TreeNode* node) {
//         if(!node->left && ! node->right) {
//             //第一种情况，该节点没有左右孩子
//             delete node;
//             return NULL;
//         } else if (node->left && !node->right) {
//             //第二种情况，有左孩子，没有右孩子
//             TreeNode* tmp = node->left;
//             delete node;
//             return tmp;
//         } else if (!node->left && node->right) {
//             //第三种情况，没有左孩子，有右孩子
//             TreeNode* tmp = node->right;
//             delete node;
//             return tmp;
//         } else {
//             //最后一种情况，左右孩子都存在
//             // TreeNode* parent = root;
//             TreeNode* tmp = node->left;
//             while(tmp->right) {
//                 tmp = tmp->right;
//             }
//             tmp->right = node->right;
//             tmp = node->left;
//             delete node;
//             return tmp;
//         }       
//     }


// 递归遍历
public:
    TreeNode* deleteNode(TreeNode* root, int val) {
        
        if(root == NULL) return root;
        if(root->val == val) {
            // 以下做的事情是：
            // 因为已经找到了要删除的节点，
            // 这里不需要链上，需要做的是删除当前的节点，并创建那个要被链上的节点，
            if(!root->left && ! root->right) {
                //第一种情况，该节点没有左右孩子
                delete root;
                return NULL;
            } else if (root->left && !root->right) {
                //第二种情况，有左孩子，没有右孩子
                TreeNode* tmp = root->left;
                delete root;
                return tmp;
            } else if (!root->left && root->right) {
                //第三种情况，没有左孩子，有右孩子
                TreeNode* tmp = root->right;
                delete root;
                return tmp;
            } else {
                //最后一种情况，左右孩子都存在
                // TreeNode* parent = root;
                TreeNode* tmp = root->left;
                while(tmp->right) {
                    tmp = tmp->right;
                }
                tmp->right = root->right;
                tmp = root->left;
                delete root;
                return tmp;
            }
        }

        // 在递归遍历的过程中，路径是有顺序的走着，直到找到了那个要删除的节点
        // 找到了之后，以上的操作就是处理被找到的节点，返回处理完的节点
        // 这时候，把他连接上去，即可
        if(root->val > val) root->left = deleteNode(root->left, val);
        if(root->val < val) root->right = deleteNode(root->right, val);

        return root;
    }
};
// @lc code=end

